class Solution {
public:
    bool isMatch(string s, string p) {
        int i = s.length() - 1, j = p.length() - 1, k;
        while(j >= 0) {
            if(p[j] >= 'a' && p[j] <= 'z') {
                if(i < 0) return false;
                if(p[j] == s[i]) {
                    --j;
                    --i;
                } else {
                    return false;
                }
            } else if(p[j] == '.') {
                if(i < 0) return false;
                --j;
                --i;
            } else if(p[j] == '*') {
                if(j - 1 >= 0 && p[j - 1] == '.') {
                    for(k = i; k >= 0; --k) {
                        if(isMatch(s.substr(0, k), p.substr(0, j - 1))) {
                            return true;
                        }
                    }
                    j = j - 2;
                } else if(j - 1 >= 0 && p[j - 1] >= 'a' && p[j - 1] <= 'z') {
                    for(k = i; k >= 0; --k) {
                        if(s[k] == p[j - 1]) {
                            if(isMatch(s.substr(0, k), p.substr(0, j - 1))) {
                                return true;
                            }
                        } else {
                            break;
                        }
                    }
                    j = j - 2;
                } else {
                    return false;
                }
            }
        }
        if(i < 0 && j < 0) return true;
        else return false;
    }
};
